题解 AT3577@洛谷 | 3577@AtCoder 【Largest Smallest Cyclic Shift】

这题在 AtCoder 的评分是 3266，感觉肯定是黑题，但是咋就通过了呢（

题意翻译的不够清楚，重新解释一遍：（做这题的时候看了好久也没看懂，然后就去原题看英文题面了）

定义 $f(S)$ 为：对于一个字符串 $S$，每次将它最左边的字符放置到字符串末尾生成的字符串集合中，字典序最小的字符串。例如：对于 $S$ 为 bcbca 的情况，$f(S)$ 即为 babca、abcab、bcaba、cabab、abcbc 中最小的那个，即 abcbc。

你需要构造一个字符串 $T$，共包含 $X$ 个字符 a、$Y$ 个字符 b 和 $Z$ 个字符 c，使得 $f(T)$ 尽可能大，输出这个 $f(T)$。

思路：

要使得 $f(T)$ 尽可能大，每次循环求一遍显然不现实，最好构造出一种 $T$ 使得它本身就是 $f(T)$（即：$T=f(T)$）。

那么怎么构造呢？

我们可以使用 multiset 来记录所有供选择的字符串，每次合并两个字符串，直到集合中只剩一个为止。合并的方法是取最小的字符串 $a$ 与最大的字符串 $b$，将 $b$ 拼接到 $a$ 后面，重新加入集合。

这种情况下，这个前缀因为是最小的，所以从任何其它地方开头取字符串均不会更小，保证了 $T=f(T)$。

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define loop while(true)
#define rep(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define per(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
#define fil(x,y) memset((x), (y), sizeof(x))
using namespace std;
typedef long long ll;

int x, y, z; multiset<string> qwq;

int main() {
	scanf("%d%d%d", &x, &y, &z);
	rep(i, 1, x) qwq.insert("a");
	rep(i, 1, y) qwq.insert("b");
	rep(i, 1, z) qwq.insert("c");
	while(qwq.size() ^ 1) {
		multiset<string>::iterator         it1 = qwq.begin();
		multiset<string>::reverse_iterator it2 = qwq.rbegin();
		string a = (*it1), b = (*it2), _ = a + b;
		qwq.erase(qwq.lower_bound(a)); qwq.erase(qwq.lower_bound(b));
		qwq.insert(_);
	}
	multiset<string>::iterator it = qwq.begin();
	cout<<(*it)<<endl;
	return 0;
}

（顺带一提，无意中还抢到了 R42600000，虽然有个地方错了 QAQAQ）